| 数据结构与算法基础 | 您所在的位置：网站首页 › makefile 遍历目录 › 数据结构与算法基础 |
数据结构与算法基础
|
目录 一、遍历定义 二、遍历实质 三、DFS 四、BFS 五、宏定义 六、自定义类型 七、函数实现 1、DFS（邻接矩阵实现） 2、DFS（邻接表实现） 3、BFS（邻接矩阵实现） 4、BFS（邻接表实现） 5、打印邻接矩阵遍历顺序 6、打印邻接表遍历顺序 八、遍历算法效率分析 1、DFS 2、BFS 九、Linux编译测试 一、遍历定义从已给的连通图中某一顶点出发，沿着一些边访问遍图中所有顶点，且使每个顶点仅被访问一次，就叫做的图的遍历，它是图的基本运算。 二、遍历实质找每个顶点的邻接点的过程。 三、DFS深度优先搜索，英文全称Depth First Search。如下图进行举例说明。
这里以邻接矩阵表示无向图进行举例，生成内容如下： [2023-5]--[ Debug ]--Printf AMGraph : VertexArray : [A ,B ,C ,D ,E ] ArcArray : [32767 ,20 ,30 ,10 ,32767 ] [20 ,32767 ,32767 ,32767 ,50 ] [30 ,32767 ,32767 ,40 ,32767 ] [10 ,32767 ,40 ,32767 ,60 ] [32767 ,50 ,32767 ,60 ,32767 ] CurVertexNum : 5 CurArcNum : 12我们还需要维护一个Visit数组，用于确认访问过的节点有哪些，0表示没有访问过，1表示访问过。
例如我们从E出发，Visit数组变为：
从邻接矩阵上看，E->B和E->D，DFS算法是一条道走到黑，先扫到B节点，又发现B节点没有被访问，所以先走E->B。 [32767 ,50 ,32767 ,60 ,32767 ]Visit数组变为：
从邻接矩阵上看B的情况，可以走B->A和B->E，先发现的A节点，又发现A节点没有被访问，所以先走B->A。 [20 ,32767 ,32767 ,32767 ,50 ]Visit数组变为：
从邻接矩阵上看A的情况，可以走A->B和A->C，A->D，先发现的B节点，又发现B节点被访问过，所以跳过，再看C节点发现没有被访问，所以先走A->C。 [32767 ,20 ,30 ,10 ,32767 ]Visit数组变为：
从邻接矩阵上看C的情况，可以走C->A和C->D，先发现的A节点，又发现A节点被访问过，所以跳过，再看D节点发现没有被访问，所以先走C->D。 [30 ,32767 ,32767 ,40 ,32767 ]Visit数组变为：
最后发现Visit数组中的所有节点被访问完，退出程序。 四、BFS广度优先搜索，英文全称Breadth First Search，BFS类似于树的层次遍历，我们可以将图逆时针旋转90度，如下图进行举例说明。
旋转后：
这里以邻接矩阵表示无向图进行举例，生成内容如下： [2023-5]--[ Debug ]--Printf AMGraph : VertexArray : [A ,B ,C ,D ,E ] ArcArray : [32767 ,20 ,30 ,10 ,32767 ] [20 ,32767 ,32767 ,32767 ,50 ] [30 ,32767 ,32767 ,40 ,32767 ] [10 ,32767 ,40 ,32767 ,60 ] [32767 ,50 ,32767 ,60 ,32767 ] CurVertexNum : 5 CurArcNum : 12和DFS一样我们也需要维护一个Visit数组，用于确认访问过的节点有哪些，0表示没有访问过，1表示访问过。
我们还需要维护一个队列，没错思路和层次遍历一样。 例如我们还是从E出发，Visit数组变为：
队列变为： [2023-5]--[ Debug ]--SqQueue Data : Data : [ 4 ] FrontIndex : 0 RearIndex : 1 SqQueueLen : 1从邻接矩阵上看E，E->B和E->D，BFS算法是广度优先，会先把E可以访问的节点先都走一遍，判断BD是否被访问，都没有被访问，那就依次访问E->B和E->D。 [32767 ,50 ,32767 ,60 ,32767 ]Visit数组变为：
队列弹出E，压入BD变为： [2023-5]--[ Debug ]--SqQueue Data : Data : [ 1 ,3 ] FrontIndex : 1 RearIndex : 3 SqQueueLen : 2队列中弹出B，从邻接矩阵上看B的情况，可以走B->A和B->E，发现A节点没有被访问,压入队列中，E被访问过，不压入，所以走B->A。 [20 ,32767 ,32767 ,32767 ,50 ]Visit数组变为：
队列，弹出B，压入A变为： [2023-5]--[ Debug ]--SqQueue Data : Data : [ 3 ,0 ] FrontIndex : 2 RearIndex : 4 SqQueueLen : 2弹出D,从邻接矩阵上看D的情况，可以走D->A和D->C，D->E，发现A节点被访问过，所以跳过，再看C节点发现没有被访问，所以先走D->C，发现所有节点都被访问，退出程序。 [10 ,32767 ,40 ,32767 ,60 ]Visit数组变为：
这是一个访问顺序数组，方便查看访问顺序的。 邻接矩阵和邻接表的定义和相关代码可以参考之前的文章《数据结构与算法基础-学习-23-图之邻接矩阵与邻接表》 七、函数实现 1、DFS（邻接矩阵实现） void DepthFirstSearchUseAMGraph(AMGraph* AMG, VertexIndexType VertexIndex, VertexIndexType* VisitedArray, AccessSeqType* AccessSeq) { AccessSeq->Array[AccessSeq->ArraySize] = VertexIndex; AccessSeq->ArraySize++; VisitedArray[VertexIndex] = VISITED_FLAG; VertexIndexType ColIndex; if(AccessSeq->ArraySize == AMG->CurVertexNum)//如果所有结点访问完成，退出。 { return; } //GlobalCnt++; for(ColIndex = 0; ColIndex < AMG->CurVertexNum; ColIndex++) { //GlobalCycleCnt++; if(AMG->ArcArray[VertexIndex][ColIndex] != MAX_INT_TYPE_NUM && VisitedArray[ColIndex] == NOT_VISITED_FLAG) { DepthFirstSearchUseAMGraph(AMG, ColIndex, VisitedArray, AccessSeq); if(AccessSeq->ArraySize == AMG->CurVertexNum)//如果所有结点访问完成，退出。 { break; } } } } 参数名描述AMG邻接矩阵。VertexIndex从哪个顶点索引号开始搜索。VisitedArray顶点访问数组。AccessSeq顶点访问顺序数组。 2、DFS（邻接表实现） void DepthFirstSearchUseAGraph(AGraph* AG, VertexIndexType VertexIndex, VertexIndexType* VisitedArray, AccessSeqType* AccessSeq) { AccessSeq->Array[AccessSeq->ArraySize] = VertexIndex; AccessSeq->ArraySize++; VisitedArray[VertexIndex] = VISITED_FLAG; //GlobalCnt++; if(AccessSeq->ArraySize == AG->VertexNum)//如果所有结点访问完成，退出。 { return; } ArcNode* TmpArcNode = AG->Vertices[VertexIndex].FirstArcNodePtr;; while(TmpArcNode != NULL) { //GlobalCycleCnt++; if(VisitedArray[TmpArcNode->EndVertexIndex] == NOT_VISITED_FLAG) { DepthFirstSearchUseAGraph(AG, TmpArcNode->EndVertexIndex, VisitedArray, AccessSeq); if(AccessSeq->ArraySize == AG->VertexNum)//如果所有结点访问完成，退出。 { break; } } TmpArcNode = TmpArcNode->NextNodePtr; } } 参数名描述AG邻接表。VertexIndex从哪个顶点索引号开始搜索。VisitedArray顶点访问数组。AccessSeq顶点访问顺序数组。 3、BFS（邻接矩阵实现） void BreadthFirstSearchUseAMGraph(AMGraph* AMG, VertexIndexType VertexIndex, VertexIndexType* VisitedArray, AccessSeqType* AccessSeq) { JudgeAllNullPointer(VisitedArray); JudgeAllNullPointer(AccessSeq); SqQueue* SQ = NULL; VertexIndexType* TmpElem = (VertexIndexType*)MyMalloc(sizeof(VertexIndexType)); VertexIndexType i = 0; InitSqQueue(&SQ,INT_TYPE_FLAG);//初始化循环顺序队 EnterSqQueue(SQ, &VertexIndex);//将第一个结点压入循环顺序队。 VisitedArray[VertexIndex] = VISITED_FLAG; AccessSeq->Array[AccessSeq->ArraySize] = VertexIndex; AccessSeq->ArraySize++; while(GetSqQueueLen(SQ) != 0) { PrintfSqQueue(SQ); LeaveSqQueue(SQ, TmpElem); for(i = 0; i < AMG->CurVertexNum; i++) { if(AMG->ArcArray[*TmpElem][i] != MAX_INT_TYPE_NUM && VisitedArray[i] == NOT_VISITED_FLAG) { EnterSqQueue(SQ, &i); VisitedArray[i] = VISITED_FLAG; AccessSeq->Array[AccessSeq->ArraySize] = i; AccessSeq->ArraySize++; if(AccessSeq->ArraySize == AMG->CurVertexNum)//如果所有结点访问完成，退出。 { break; } } } if(AccessSeq->ArraySize == AMG->CurVertexNum)//如果所有结点访问完成，退出。 { break; } } DestroySqQueue(&SQ); free(TmpElem); TmpElem = NULL; Log("Breadth First Search Use AMGraph OK\n",Debug); } 参数名描述AMG邻接矩阵。VertexIndex从哪个顶点索引号开始搜索。VisitedArray顶点访问数组。AccessSeq顶点访问顺序数组。感觉访问顺序数组满退出这一块，两次break，写成goto是不是好些，大家有想法的可以指点小弟一二。 4、BFS（邻接表实现） void BreadthFirstSearchUseAGraph(AGraph* AG, VertexIndexType VertexIndex, VertexIndexType* VisitedArray, AccessSeqType* AccessSeq) { JudgeAllNullPointer(VisitedArray); JudgeAllNullPointer(AccessSeq); SqQueue* SQ = NULL; VertexIndexType* TmpElem = (VertexIndexType*)MyMalloc(sizeof(VertexIndexType)); ArcNode* TmpNode = NULL; InitSqQueue(&SQ,INT_TYPE_FLAG);//初始化循环顺序队 EnterSqQueue(SQ, &VertexIndex);//将第一个结点压入循环顺序队。 VisitedArray[VertexIndex] = VISITED_FLAG; AccessSeq->Array[AccessSeq->ArraySize] = VertexIndex; AccessSeq->ArraySize++; while(GetSqQueueLen(SQ) != 0) { LeaveSqQueue(SQ, TmpElem); TmpNode = AG->Vertices[*TmpElem].FirstArcNodePtr; while(TmpNode != NULL) { if(VisitedArray[TmpNode->EndVertexIndex] == NOT_VISITED_FLAG) { EnterSqQueue(SQ, &(TmpNode->EndVertexIndex)); VisitedArray[TmpNode->EndVertexIndex] = VISITED_FLAG; AccessSeq->Array[AccessSeq->ArraySize] = TmpNode->EndVertexIndex; AccessSeq->ArraySize++; if(AccessSeq->ArraySize == AG->VertexNum)//如果所有结点访问完成，退出。 { break; } } TmpNode = TmpNode->NextNodePtr; } if(AccessSeq->ArraySize == AG->VertexNum)//如果所有结点访问完成，退出。 { break; } } DestroySqQueue(&SQ); free(TmpElem); TmpElem = NULL; Log("Breadth First Search Use AGraph OK\n",Debug); } 参数名描述AG邻接表。VertexIndex从哪个顶点索引号开始搜索。VisitedArray顶点访问数组。AccessSeq顶点访问顺序数组。 5、打印邻接矩阵遍历顺序 Status AMGraphTraverse(void (*Func)(AMGraph*,VertexIndexType,VertexIndexType*, AccessSeqType*),AMGraph* AMG, VertexIndexType VertexIndex) { JudgeAllNullPointer(AMG); VertexIndexType* VisitedArray = (VertexIndexType*)MyCalloc(AMG->CurVertexNum, sizeof(VertexIndexType)); AccessSeqType* AccessSeq = (AccessSeqType*)MyCalloc(1, sizeof(AccessSeqType)); AccessSeq->ArraySize = 0; Func(AMG, VertexIndex, VisitedArray, AccessSeq); char* string = (char*)MyCalloc(STR_TYPE_SIZE, sizeof(char)); CopyStr* PS = (CopyStr*)malloc(sizeof(CopyStr)); InitCopyStr(PS); ExecCopyStr(PS,"Traverse Use AMGraph : ["); VertexIndexType i; for(i = 0; i < AccessSeq->ArraySize; i++) { sprintf(string,"%d ,", AccessSeq->Array[i]); ExecCopyStr(PS,string); } PS->String[PS->StrEffectiveLen-1] = ']'; ExecCopyStr(PS,"\n"); free(AccessSeq); free(VisitedArray); AccessSeq = NULL; VisitedArray = NULL; PS->String[PS->StrEffectiveLen] = '\0'; Log(PS->String, Debug); DestroyCopyStr(PS); free(string); string = NULL; return SuccessFlag; } 参数名描述FuncDFS或BFS函数指针。AMG邻接矩阵。VertexIndex从哪个顶点索引号开始搜索。 6、打印邻接表遍历顺序 Status AGraphTraverse(void (*Func)(AGraph*,VertexIndexType,VertexIndexType*,AccessSeqType*),AGraph* AG, VertexIndexType VertexIndex) { JudgeAllNullPointer(AG); VertexIndexType* VisitedArray = (VertexIndexType*)MyCalloc(AG->VertexNum, sizeof(VertexIndexType)); AccessSeqType* AccessSeq = (AccessSeqType*)MyCalloc(1, sizeof(AccessSeqType)); AccessSeq->ArraySize = 0; Func(AG, VertexIndex, VisitedArray, AccessSeq); char* string = (char*)MyCalloc(STR_TYPE_SIZE, sizeof(char)); CopyStr* PS = (CopyStr*)malloc(sizeof(CopyStr)); InitCopyStr(PS); ExecCopyStr(PS,"Traverse Use AGraph : ["); VertexIndexType i; for(i = 0; i < AccessSeq->ArraySize; i++) { sprintf(string,"%d ,", AccessSeq->Array[i]); ExecCopyStr(PS,string); } PS->String[PS->StrEffectiveLen-1] = ']'; ExecCopyStr(PS,"\n"); free(AccessSeq); free(VisitedArray); AccessSeq = NULL; VisitedArray = NULL; PS->String[PS->StrEffectiveLen] = '\0'; Log(PS->String, Debug); DestroyCopyStr(PS); free(string); string = NULL; return SuccessFlag; } 参数名描述FuncDFS或BFS函数指针。AG邻接表。VertexIndex从哪个顶点索引号开始搜索。 八、遍历算法效率分析 1、DFS用邻接矩阵表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n^2)。 用邻接表表示图，虽然有2e个表结点，但只需要扫描e个结点即可完成遍历，加上访问n个头节点的时间，时间复杂度为O(n+e)。 2、BFS使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n个元素），总的时间代价为O(n^2)。 用邻接表表示图，虽然有2e个表结点，但只需要扫描e个结点即可完成遍历，加上访问n个头节点的时间，时间复杂度为O(n+e)。 九、Linux编译测试 [gbase@czg2 Graph]$ make gcc -Wall -Wextra -O3 ../Log/Log.c ../PublicFunction/PublicFunction.c ../PublicFunction/SqQueue/SqQueue.c Graph.c MinimumSpanningTree.c main.c -o TestGraph -I ../Log/ -I ../PublicFunction/ -I ../Select/ -I ../PublicFunction/SqQueue/ [gbase@czg2 Graph]$ ./TestGraph [2023-5]--[ Info ]--Create Net Data : OK [2023-5]--[ Info ]--Create Undirection Net Use AMGraph : OK [2023-5]--[ Debug ]--Printf AMGraph : VertexArray : [A ,B ,C ,D ,E ] ArcArray : [32767 ,20 ,30 ,10 ,32767 ] [20 ,32767 ,32767 ,32767 ,50 ] [30 ,32767 ,32767 ,40 ,32767 ] [10 ,32767 ,40 ,32767 ,60 ] [32767 ,50 ,32767 ,60 ,32767 ] CurVertexNum : 5 CurArcNum : 12 [2023-5]--[ Info ]--Create Undirection Net Use AGraph : OK [2023-5]--[ Debug ]--Printf AGraph : A : [(2, 30, 0x6f18b0),(1, 20, 0x6f1870),(3, 10, (nil))] B : [(4, 50, 0x6f18d0),(0, 20, (nil))] C : [(3, 40, 0x6f1910),(0, 30, (nil))] D : [(4, 60, 0x6f1950),(2, 40, 0x6f1890),(0, 10, (nil))] E : [(3, 60, 0x6f1990),(1, 50, (nil))] VertexNum : 5 ArcNum : 12 [2023-5]--[ Debug ]--Traverse Use AMGraph : [4 ,1 ,0 ,2 ,3 ] [2023-5]--[ Debug ]--Traverse Use AGraph : [4 ,3 ,2 ,0 ,1 ] [2023-5]--[ Debug ]--Init SqQueue Normal [2023-5]--[ Debug ]--Enter SqQueue Normal [2023-5]--[ Debug ]--SqQueue Data : Data : [ 4 ] FrontIndex : 0 RearIndex : 1 SqQueueLen : 1 Flag : INT_TYPE_FLAG [2023-5]--[ Debug ]--Leave SqQueue Normal [2023-5]--[ Debug ]--Enter SqQueue Normal [2023-5]--[ Debug ]--Enter SqQueue Normal [2023-5]--[ Debug ]--SqQueue Data : Data : [ 1 ,3 ] FrontIndex : 1 RearIndex : 3 SqQueueLen : 2 Flag : INT_TYPE_FLAG [2023-5]--[ Debug ]--Leave SqQueue Normal [2023-5]--[ Debug ]--Enter SqQueue Normal [2023-5]--[ Debug ]--SqQueue Data : Data : [ 3 ,0 ] FrontIndex : 2 RearIndex : 4 SqQueueLen : 2 Flag : INT_TYPE_FLAG [2023-5]--[ Debug ]--Leave SqQueue Normal [2023-5]--[ Debug ]--Enter SqQueue Normal [2023-5]--[ Debug ]--Destroy SqQueue Normal [2023-5]--[ Debug ]--Breadth First Search Use AMGraph OK [2023-5]--[ Debug ]--Traverse Use AMGraph : [4 ,1 ,3 ,0 ,2 ] [2023-5]--[ Debug ]--Init SqQueue Normal [2023-5]--[ Debug ]--Enter SqQueue Normal [2023-5]--[ Debug ]--Leave SqQueue Normal [2023-5]--[ Debug ]--Enter SqQueue Normal [2023-5]--[ Debug ]--Enter SqQueue Normal [2023-5]--[ Debug ]--Leave SqQueue Normal [2023-5]--[ Debug ]--Enter SqQueue Normal [2023-5]--[ Debug ]--Enter SqQueue Normal [2023-5]--[ Debug ]--Destroy SqQueue Normal [2023-5]--[ Debug ]--Breadth First Search Use AGraph OK [2023-5]--[ Debug ]--Traverse Use AGraph : [4 ,3 ,1 ,2 ,0 ] [2023-5]--[ Info ]--Destory Net Data : OK [2023-5]--[ Info ]--Destory Undirection Net Use AMGraph: OK [2023-5]--[ Info ]--Destory Undirection Net Use AGraph : OK |
【本文地址】
公司简介
联系我们
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |